// https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/
// 给你 root1 和 root2 这两棵二叉搜索树。请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
struct TreeNode{
	int val;
	TreeNode * left;
	TreeNode * right;
	TreeNode() : val(0), left(nullptr), right(nullptr){}
	TreeNode(int x): val(x), left(nullptr), right(nullptr){}
	TreeNode(int x, TreeNode * left, TreeNode * right) : val(x), left(left), right(right) {}
};

 
class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
		vector<int> res1;
		vector<int> res2;
		showMid(root1, res1);
		showMid(root2, res2);
		int len1 = res1.size();
		int len2 = res2.size();
		int i = 0, j = 0;
		vector<int> res;
		while(i < len1 && j < len2){
			if(res1[i] <= res2[j]){
				res.push_back(res1[i]);
				i++;
			} else {
				res.push_back(res2[j]);
				j++;
			}
		}
		
		while(i < len1){
			res.push_back(res1[i]);
			i++;
		}
		while(j < len2){
			res.push_back(res2[j]);
			j++;
		}
		return res;
    }
	
	void showMid(TreeNode * head, vector<int> & res){
		if(head){
			showMid(head->left, res);
			res.push_back(head->val);
			showMid(head->right, res);
		}
	}
	
	TreeNode * init1(){
		return nullptr;
		TreeNode * n1 = new TreeNode(2);
		TreeNode * n2 = new TreeNode(1);
		TreeNode * n3 = new TreeNode(4);
		n1->left = n2;
		n1->right = n3;
		return n1;
	}
	
	TreeNode * init2(){
		TreeNode * n1 = new TreeNode(2);
		TreeNode * n2 = new TreeNode(0);
		TreeNode * n3 = new TreeNode(1);
		TreeNode * n4 = new TreeNode(5);
		TreeNode * n5 = new TreeNode(7);
		n1->left = n3;
		n1->right = n4;
		n3->left = n2;
		n4->right = n5;
		
		return n1;
	}
};

int main(){
	Solution so;
	TreeNode * n1 = so.init1();
	TreeNode * n2 = so.init2();
	
	vector<int> res = so.getAllElements(n1, n2);
	for(auto i : res){
		cout << i << ",";
	}
	cout << endl;
	return 0;
}